package com.leetCode.zero;

import java.lang.reflect.Method;
import java.lang.reflect.Type;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

/**
 * Given a string s, find the longest palindromic substring in s. You may assume
 * that the maximum length of s is 1000.
 * 
 * Example:
 * 
 * Input: "babad"
 * 
 * Output: "bab"
 * 
 * Note: "aba" is also a valid answer.
 * 
 * 
 * Example:
 * 
 * Input: "cbbd"
 * 
 * Output: "bb"
 * 
 * @author lyk
 *
 */
public class Problem05 {
	public static void main(String[] args) throws Exception {
		Solution s = getInstance();
		Type a = "String".getClass();
		HashMap<String, String> hm = new HashMap<>();
		hm.put("babad", "bab");
		hm.put("cbbd", "bb");
		hm.put("bb", "bb");
		hm.put("abcdasdfghjkldcba", "a");
		Set<Entry<String,String>> entrySet = hm.entrySet();
		for (Entry<String, String> entry : entrySet) {
			String key = entry.getKey();
			String value = entry.getValue();
			if(value.equals(s.longestPalindrome(key))){
				System.out.println(key+":"+s.longestPalindrome(key)+"===>"+true);
			}else{
				System.out.println(key+":"+s.longestPalindrome(key)+"===>"+false);
			}
		}
		String k = "e1baabb";
		System.out.println(k+":"+s.longestPalindrome(k));
		
	}

	class Solution {
		public String longestPalindrome(String s) {
			String[] split = s.split("");
			String res = s.substring(0,1);
			int result = 1;
			int length = s.length();
			//判断奇数个回文
			for (int i = 1; i < length-1; i++) {
				int left = i-1;
				int right = i+1;
				int temp = 1;
//				System.out.println("开始奇数判断"+s+":"+split[i]);
				while(left>=0 && right < length ){
//					System.out.println("全部"+s.substring(left, right+1));
//					System.out.println(left+":"+right);
					if(split[left].contentEquals(split[right])){
						temp+=2;
						if(temp>result){
							result = temp;
							res = s.substring(left,right+1);
//							System.out.println("找到回文" + res);
						}
					}else{
						break;
					}
					left--;
					right++;
				}
				
			}
			//判断偶数个回文
			for (int i = 0; i < length-1; i++) {
//				System.out.println("开始偶数判断"+s+":"+split[i]);
				if(!split[i].equals(split[i+1])){
					continue;
				}
				int temp = 2;
				if(temp>result){
					result = temp;
					res = s.substring(i,i+2);
//					System.out.println("找到回文" + res);
				}
				int left = i-1;
				int right = i+2;

				while(left>=0 && right < length ){
//					System.out.println("全部"+s.substring(left, right+1));
//					System.out.println(left+":"+right);
					if(split[left].contentEquals(split[right])){
						temp+=2;
						if(temp>result){
							result = temp;
							res = s.substring(left,right+1);
//							System.out.println("找到回文" + res);
						}
					}else{
						break;
					}
					left--;
					right++;
				}
			}
			return res;
		}
	}

	static Solution getInstance() throws Exception {
		String className = Thread.currentThread().getStackTrace()[1].getClassName();
		Class<?> forName = Class.forName(className);
		Method method = forName.getMethod("newS", null);
		Solution solution = (Solution) method.invoke(forName.newInstance(), null);
		return solution;
	}

	public Solution newS() {
		return new Solution();
	}
}
